package com.leetcode;

public class Leetcode121 {
    /*
    //solution 1:
    public int maxProfit(int[] prices) {
        int res = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            //记录最低值
            if (prices[i] < min) {
                min = prices[i];
            } else {
                //记录最大的收益
                if (prices[i] - min > res) {
                    res = prices[i] - min;
                }
            }
        }

        return res;
    }
*/
    //solution 2:动态规划
    //我们只需要考虑当天买和前一天买哪个收益更高，
    public int maxProfit(int[] prices) {
        int n = prices.length;
        //buy表示买入，同时也表示最低的买入价格
        int buy = -prices[0];
        //sell表示卖出，同时也表示最大收益
        int sell = 0;

        for(int i=1; i<n; i++){
            //记录买入的价格
            //买入，资金减少,因此需要-prices[i];
           buy = Math.max(buy,-prices[i]);
           //记录卖出的价格
           //卖出，资金增加,因此需要+prices[i]
           sell = Math.max(sell,buy+prices[i]);
        }

        return sell;
    }

    public static void main(String[] args) {
        Leetcode121 leetcode = new Leetcode121();
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(leetcode.maxProfit(prices));
    }
}
